#include <iostream>
using std::cout;
using std::endl;

static const int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
static int tofind = 7;

// 二分查找，返回索引
int BinarySearch(const int arr[], int size, int data) {
  int low = 0, high = size - 1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (arr[mid] == data) {
      return mid;
    } else if (arr[mid] > data) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}
void TestBinarySearch() {
  int idx = BinarySearch(arr, sizeof(arr) / sizeof(int), tofind);
  cout << "idx:" << idx << endl;
}

// 递归二分查找，返回索引
int RecurBinarySearch(const int arr[], int first, int last, int data) {
  if (first > last) return -1;
  int mid = (first + last) / 2;
  if (arr[mid] == data) {
    return mid;
  } else if (arr[mid] > data) {
    return RecurBinarySearch(arr, first, mid - 1, data);
  } else {
    return RecurBinarySearch(arr, mid + 1, last, data);
  }
}
void TestRecurBinarySearch() {
  int idx = RecurBinarySearch(arr, 0, sizeof(arr) / sizeof(int) - 1, tofind);
  cout << "idx:" << idx << endl;
}

int main() {
  tofind = 3;
  TestBinarySearch();
  TestRecurBinarySearch();

  tofind = -3;
  TestBinarySearch();
  TestRecurBinarySearch();

  tofind = 13;
  TestBinarySearch();
  TestRecurBinarySearch();
}
